package com.cdream.basic.algorithm.leetcode.array;

/**
 * @author cdream
 * @date 8/7/21
 */
public class Question457 {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        boolean[] used = new boolean[n];
        for(int i = 0; i<n; i++){
            // 如果当前位置已经被走过
            if(used[i]) continue;
            used[i] = true;
            // 下个位置
            int nextIndex1 = (i + nums[i] + 1000 *n ) % n;
            // 和自己相等
            if(nextIndex1==i) continue;
            while(!used[nextIndex1]){
                used[nextIndex1] = true;
                int mid =  (nextIndex1 + nums[nextIndex1] + 1000 *n ) % n;
                if(i==mid){
                    return true;
                }
                if(nextIndex1==mid){
                    break;
                }
                nextIndex1 = mid;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        new Question457().circularArrayLoop(new int[]{2,-1,1,-2,-2});
    }
}
